The invention relates to the display of digital images, and in particular to a system for displaying, in substantially real-time, an image-mosaic consisting of a plurality of tile images.
In the field of reverse engineering of semiconductor integrated circuits (IC), surfaces of sample ICs are micro-imaged as the sample ICs are deconstructed for purposes of design and layout extraction. The micro-images are displayed at a workstation to permit an analyst to extract the design and layout of the IC. The data required to display the images is characterized by being complex, and it may require processing prior to its display.
As described in co-pending application Ser. No. 09/594,169, filed Jun. 15, 2000, and entitled xe2x80x9cMETHOD AND SYSTEM FOR RECALIBRATION DURING MICRO-IMAGING TO DETERMINE THERMAL DRIFTxe2x80x9d, the image data is acquired in increments. Each increment is a tile image constituent of an image-mosaic. Each image-mosaic is representative of a surface of interest of a sample IC die at a deconstructive step in reverse engineering the IC. Tile images are typically stored in a high capacity data storage.
In order to extract design and layout information from the image data, selected groups of tile images are requested from the high capacity data storage, assembled into portions of image-mosaics, and the assembled portions of image-mosaics are displayed on a man-machine interface. The selected groups of tile images are representative of a specific area of the surface of interest of the sample IC, at a specific deconstructive step and at a specific magnification. The analyst visually inspects the image-mosaics to extract design and layout information therefrom.
Typically, the man-machine interface is implemented on a computer workstation associated with a Local Area Network (LAN). Modern computer workstations are well suited for data processing, but have limited storage capacity relative to the amount of image data required to be manipulated in reverse-engineering an IC. The high capacity storage is typically associated with a network node on the LAN.
In an arrangement as just described, the workstation is generally programmed to perform the following tasks: respond to analyst input in real-time; provide a smooth, substantially real-time display of the image data; process reverse-engineering tasks in near real-time, etc. Typically these tasks are computationally intensive and require a proportion of the processing time of the workstation.
To provide a substantially real-time display of the image data, data manipulation intensive computations are required to refresh the display. Remote access to the tile image data from the high capacity storage via the LAN is relatively slow and unsuitable for real-time update of mosaic-views. Network data transfers are slow compared to data transfers and manipulations internal to the workstation. One way to reduce the transfer delay is to store the image data in a compressed format at the high capacity storage. The compressed data can be transferred over the LAN in the same compressed format and decompressed at the workstation.
Another way to increase the responsiveness of the man-machine interface is to cache image data at the workstation. Since storage capacity is limited at the workstation, only the image data required for the display is kept. Further benefits may be gained by caching image data in expectation of its imminent use. This is known as predictive caching. Data caching heuristics are required to optimize predictive caching. The caching heuristics relate to the way an analyst uses the man-machine interface to extract design and layout information. Extraction of design and layout information consists of two principal tasks: identification of components and component interconnections. Identification of components requires the display of an area-of-interest including the components. Identification of component interconnections requires that the analyst follow traces that may traverse at least one image-mosaic representative of the sample IC.
Various caching methods of improving image processing speed are known. The most relevant to the present invention are look-ahead caching and context caching.
U.S. patent application Ser. No. 6,016,520 entitled METHOD OF VIEWING AT A CLIENT. VIEWING STATION A MULTIPLE MEDIA TITLE STORED AT A SERVER AND CONTAINING A PLURALITY OF TOPICS UTILIZING ANTICIPATORY CACHING, which issued on Jan. 18, 2000 to Facq et al. describes an implementation of context based anticipatory caching of media content in providing client-initiated server-driven remote service provision. The issue addressed is the length of time required to search a database of information at the server and transmit the information from the server to the client viewing station. In response to an initial keyword-based request for an item of media content from the server, the remote services at the server search additional items of media content likely to be requested and transmit these items to the client viewing station in advance of their request. Transmitted items are cached by services at the client viewing station in a cache storage. The client viewing station checks the cache storage before making additional requests for transfer of multiple media items over the remote connection. Although this type of on-line multiple media system provides responsive interactive presentation of information at the client viewing station, context based caching is unsuitable for manipulating tile images in reverse-engineering a sample IC, largely because it does not accommodate an expression of a xe2x80x9cnearxe2x80x9d or xe2x80x9cadjacentxe2x80x9d content.
Look-ahead caching is used to provide a Central Processing Unit (CPU) with access to information it is likely to require in the immediate future. CPUs have very little memory available for processing, typically limited to a few registers. Information is usually available in storage, and is retrieved using a computer bus. In processing information the CPU performs a large number of fetch instructions. Typically the required information is available in Random Access Memory (RAM) such as semiconductor type memory accessible over the computer bus. The computer bus is also used by the CPU to access other devices and can therefore be slow to fetch information such as instructions or data, especially if the fetches are performed instruction-by-instruction. Modern computer buses have burst transfer capabilities or dedicated transfer capabilities, such as are provided by Direct Memory Access (DMA) controllers. Modern CPUs are provided with a local cache which is loaded or pre-loaded with a relatively large amount of data and instructions via the bursting capability of the bus or the DMA service. The CPU has dedicated access to the local cache for fetching the necessary data and instructions.
A great deal of work has been invested in the development of algorithms for loading or pre-loading the local cache with relevant information that the CPU needs. Since the data and instruction sets processed by CPUs are largely stored sequentially in files, these algorithms are based on look-ahead heuristics. Look-ahead caching, although suited for sequentially arranged information, does not address the problem associated with tile image display, because a group of displayed tile image required for display in reverse-engineering of ICs are not necessarily stored sequentially due to the two dimensional relationship between the tile images in a image-mosaic.
There is therefore a need for methods of predictively caching tile image constituents of an image-mosaic to provide a substantially smooth display of portions of the image-mosaic in real-time.
It is an object of the invention to provide a priority based caching algorithm adapted for caching tile images in accordance with a priority computed by a caching algorithm.
It is another object of the invention to control caching of image data to prevent an over utilization of system resources.
It is a further object of the invention to enable extraction of design and layout information via multiple workstations.
It is yet another object of the invention to distribute network data transfers to prevent overloading of an associated LAN used for data storage and transfer.
In accordance with one aspect of the invention an algorithm for caching tile image constituents of an image-mosaic to facilitate the panning or resizing of a mosaic-view of an event driven man-machine interface is provided. At least a portion of the image-mosaic including a plurality of tile images assembled in a contiguous, juxtaposed relationship is displayed in the mosaic-view. The algorithm makes use of a caching predictor for computing a retrieval priority for each tile image surrounding the panned or resized mosaic-view in a predetermined pattern and to a predetermined extent. A tile image retrieval process retrieves tile images from storage and adds the images to a cache in accordance with the priority assigned by the caching predictor.
In accordance with another aspect of the invention, there is provided a display apparatus for displaying, on an event driven man-machine interface, a plurality of tile images assembled into a image-mosaic. The display is a substantially smooth, real-time display of portions of the image-mosaic on the man-machine interface in response to interaction events. The apparatus includes a predictor for monitoring interaction events serviced by the man-machine interface for the purposes of prioritizing the downloading of tile images within a prediction region located in a vicinity of at least one group of displayed tile images. A retrieval queue is used for sequencing the retrieval of the tile images and a cache for storing the retrieved tile images. A scheduler controls the use of computation time used to update the cache.
The images cached are dependent on an allocated cache size, and a view change history which records a historical perspective of the most recent mosaic-views used by an analyst.
The advantages are that only tile images of highest priority are cached, while network data transfers are distributed in time on a priority basis based on probability of future demand.